{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Eight Queens LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: solveNQueens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #八皇后"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设计一种算法，打印 N 皇后在 N &times; N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的&ldquo;对角线&rdquo;指的是所有的对角线，不只是平分整个棋盘的那两条对角线。</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题相对原题做了扩展</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：4\n",
    "<strong> 输出</strong>：[[&quot;.Q..&quot;,&quot;...Q&quot;,&quot;Q...&quot;,&quot;..Q.&quot;],[&quot;..Q.&quot;,&quot;Q...&quot;,&quot;...Q&quot;,&quot;.Q..&quot;]]\n",
    "<strong> 解释</strong>: 4 皇后问题存在如下两个不同的解法。\n",
    "[\n",
    "&nbsp;[&quot;.Q..&quot;, &nbsp;// 解法 1\n",
    "&nbsp; &quot;...Q&quot;,\n",
    "&nbsp; &quot;Q...&quot;,\n",
    "&nbsp; &quot;..Q.&quot;],\n",
    "\n",
    "&nbsp;[&quot;..Q.&quot;, &nbsp;// 解法 2\n",
    "&nbsp; &quot;Q...&quot;,\n",
    "&nbsp; &quot;...Q&quot;,\n",
    "&nbsp; &quot;.Q..&quot;]\n",
    "]\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [eight-queens-lcci](https://leetcode.cn/problems/eight-queens-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [eight-queens-lcci](https://leetcode.cn/problems/eight-queens-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def dfs(i,path,total,re):\n",
    "            if i>n:\n",
    "                re.append(path)\n",
    "                return\n",
    "            for j in range(n):\n",
    "                acc = 1<<j\n",
    "                if acc&total:continue\n",
    "                flag = True\n",
    "                for k in range(1,i):\n",
    "                    tmpl, tmpr = acc<<k,acc>>k\n",
    "                    if tmpl&path[-k] or tmpr&path[-k]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    dfs(i+1,path+[acc],total|acc,re)\n",
    "        re = []\n",
    "        dfs(1,[],0,re)\n",
    "        ans = []\n",
    "        for re0 in re:\n",
    "            res = []\n",
    "            for c in re0:\n",
    "                tmp = ''\n",
    "                for i in range(n):\n",
    "                    if (c>>i)&1==1:\n",
    "                        tmp+='Q'\n",
    "                    else:\n",
    "                        tmp+='.'\n",
    "                res.append(tmp)\n",
    "            ans.append(res)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) :\n",
    "        matrix = ['.' * n for i in range(n)]\n",
    "        res = []\n",
    "        self.n = n\n",
    "        self.traverse(0, matrix, res)\n",
    "        return res\n",
    "\n",
    "    def traverse(self, row, matrix, res):\n",
    "        if row == self.n:\n",
    "            res.append(matrix[:])\n",
    "            return\n",
    "        for col in range(self.n):\n",
    "            if self.isvalid(matrix, row, col):\n",
    "                matrix[row] = matrix[row][:col] + 'Q' + matrix[row][col+1:]\n",
    "                self.traverse(row+1, matrix, res)\n",
    "                matrix[row] = matrix[row][:col] + '.' + matrix[row][col+1:]\n",
    "\n",
    "    def isvalid(self, matrix, row, col):\n",
    "        for i in range(row):\n",
    "            if matrix[i][col] == 'Q':\n",
    "                return False\n",
    "\n",
    "        i, j = row-1, col-1\n",
    "        while i >= 0 and j >= 0:\n",
    "            if matrix[i][j] == 'Q':\n",
    "                return False\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "        i, j = row-1, col+1\n",
    "        while i >= 0 and j < self.n:\n",
    "            if matrix[i][j] == 'Q':\n",
    "                return False\n",
    "            i -= 1\n",
    "            j += 1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        c = 0\n",
    "        cml = 0\n",
    "        cpl = 0\n",
    "        candidate = ['.' * i + 'Q' + '.' * (n - i - 1) for i in range(n)]\n",
    "        ans = []\n",
    "        board = []\n",
    "        def dfs(index: int, c: int, cml: int, cpl: int) -> int:\n",
    "\n",
    "            nonlocal ans, n, board\n",
    "            if index == n:\n",
    "                ans.append(list(board))\n",
    "                return 1\n",
    "            limit = c | cml | cpl\n",
    "            r = 0\n",
    "            for i in range(n):\n",
    "                x = 1 << i\n",
    "                if not (limit & x):\n",
    "                    nc = c | x\n",
    "                    ncml = (cml | x) << 1\n",
    "                    ncpl = (cpl | x) >> 1\n",
    "                    board.append(candidate[i])\n",
    "                    r += dfs(index + 1, nc, ncml, ncpl)\n",
    "                    board.pop()\n",
    "            return r\n",
    "\n",
    "        dfs(0, 0, 0, 0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        ans = []\n",
    "        left = set()\n",
    "        col = set()\n",
    "        right = set()\n",
    "        def eightqueen(temp,i):\n",
    "            if i == n:\n",
    "                res = []\n",
    "                a = ['.']*n\n",
    "                for index in temp:\n",
    "                    a[index]='Q'\n",
    "                    res.append(''.join(a))\n",
    "                    a[index]='.'\n",
    "                ans.append(res)\n",
    "            for j in range(n):\n",
    "                if j not in col and i+j not in left and i-j not in right:\n",
    "                    col.add(j)\n",
    "                    left.add(i+j)\n",
    "                    right.add(i-j)\n",
    "                    eightqueen(temp+[j],i+1)\n",
    "                    col.remove(j)\n",
    "                    left.remove(i+j)\n",
    "                    right.remove(i-j)\n",
    "        eightqueen([],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        board = [['.' for i in range(n)] for j in range(n)]\n",
    "        res = []\n",
    "        def dfs(ldia, fdia, col):\n",
    "            row = len(col)\n",
    "            if len(col) == n:\n",
    "                lis = []\n",
    "                for i in board: lis.append(''.join(i))\n",
    "                res.append(lis)\n",
    "            for i in range(n):\n",
    "                if i not in col and i + row not in ldia and i-row not in fdia:\n",
    "                    board[row][i] = 'Q'\n",
    "                    dfs(ldia+[i+row],fdia+[i-row],col+[i])\n",
    "                    board[row][i] = '.'\n",
    "        dfs([], [], [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def dfs(pre, i):\n",
    "            if i == n:\n",
    "                cur = [['.'] * n for _ in range(n)]\n",
    "                for i in range(n):\n",
    "                    cur[i][pre[i]] = 'Q'\n",
    "                queen.append([''.join(r) for r in cur])\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if j not in col and i - j not in right and i + j not in left:\n",
    "                    col.add(j)\n",
    "                    right.add(i - j)\n",
    "                    left.add(i + j)\n",
    "                    dfs(pre + [j], i + 1)\n",
    "                    col.discard(j)\n",
    "                    right.discard(i - j)\n",
    "                    left.discard(i + j)\n",
    "            return\n",
    "\n",
    "        col = set()\n",
    "        right = set()\n",
    "        left = set()\n",
    "        queen = []\n",
    "        dfs([], 0)\n",
    "        return queen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        res = []\n",
    "        def find_pos(queen, row, n):\n",
    "            for j in range(n):\n",
    "                if judge_pos(queen, row, j):\n",
    "                    queen[row][j] = 'Q'\n",
    "                    if row == n-1:\n",
    "                        copy_queen = copy.deepcopy(queen)\n",
    "                        res.append(copy_queen)\n",
    "                        queen[row][j] = '.'\n",
    "                        # queen = [['.' for j in range(n)] for i in range(n)]\n",
    "\n",
    "                    else:\n",
    "                        find_pos(queen, row+1, n)\n",
    "                        queen[row][j] = '.'\n",
    "\n",
    "\n",
    "        def judge_pos(queen, row, col):\n",
    "            for i in range(row):\n",
    "                if queen[i][col] == 'Q':\n",
    "                    return False\n",
    "                for j in range(n):\n",
    "                    if queen[i][j] == 'Q' and abs(i-row) == abs(j-col):\n",
    "                        return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        def plot_queen(queen, n):\n",
    "            out = []\n",
    "            for i in queen:\n",
    "                out.append(''.join(i))\n",
    "            return out\n",
    "\n",
    "        queen = [['.' for j in range(n)] for i in range(n)]\n",
    "        find_pos(queen, 0, n)\n",
    "\n",
    "        out = []\n",
    "        for t in res:\n",
    "            out.append(plot_queen(t, n))\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def check(j):\n",
    "            if j in st:\n",
    "                return False\n",
    "            k=len(st)\n",
    "            for i in range(k):\n",
    "                if k-i==abs(j-st[i]):\n",
    "                    return False\n",
    "            return True\n",
    "        def func():\n",
    "            nonlocal ans\n",
    "            if len(st)==n:\n",
    "                now=[]\n",
    "                for i in st:\n",
    "                    s='.'*i+'Q'+'.'*(n-i-1)\n",
    "                    now.append(s)\n",
    "                ans.append(now)\n",
    "            for i in range(n):\n",
    "                if check(i):\n",
    "                    st.append(i)\n",
    "                    func()\n",
    "                    st.pop()\n",
    "        st=[]\n",
    "        ans=[]\n",
    "        func()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        result = []\n",
    "        cur = [['.']*n for i in range(n)]\n",
    "        init = [[0]*n for i in range(n)]\n",
    "        def queen(row, cur, vis):\n",
    "            if row == n-1:\n",
    "                for col in range(n):\n",
    "                    if vis[row][col] == 0:\n",
    "                        cur[row][col] = 'Q'\n",
    "                        tmp = copy.deepcopy(cur)\n",
    "                        result.append(tmp)\n",
    "                        cur[row][col] = '.'\n",
    "                return\n",
    "            for col in range(n):\n",
    "                if vis[row][col]:\n",
    "                    continue\n",
    "                cur[row][col] = 'Q'\n",
    "                lastvis = copy.deepcopy(vis)\n",
    "                for i in range(row+1, n):\n",
    "                    for j in range(n):\n",
    "                        if j == col:\n",
    "                            vis[i][j] = 1\n",
    "                        if row+col == i+j:\n",
    "                            vis[i][j] = 1\n",
    "                        if row-col == i-j:\n",
    "                            vis[i][j] = 1\n",
    "                queen(row+1, cur, vis)\n",
    "                cur[row][col] = '.'\n",
    "                vis = lastvis\n",
    "        queen(0, cur, init)\n",
    "        res = []\n",
    "        for r in result:\n",
    "            t1 = []\n",
    "            for t2 in r:\n",
    "                ts = ''\n",
    "                for t3 in t2:\n",
    "                    ts += t3\n",
    "                t1.append(ts)\n",
    "            res.append(t1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        c = 0\n",
    "        cml = 0 # column minus row \n",
    "        cpl = 0 # column plus row\n",
    "        candidate = ['.' * i + 'Q' + '.' * (n - i - 1) for i in range(n)]\n",
    "        ans = []\n",
    "        board = []\n",
    "        def dfs(index: int, c: int, cml: int, cpl: int) -> int:\n",
    "            nonlocal ans, n, board\n",
    "            if index == n:\n",
    "                ans.append(list(board))\n",
    "                return 1\n",
    "            limit = c | cml | cpl\n",
    "            r = 0\n",
    "            for i in range(n):\n",
    "                x = 1 << i\n",
    "                if not (limit & x):\n",
    "                    board.append(candidate[i])\n",
    "                    r += dfs(index + 1, c | x, (cml | x) << 1, (cpl | x) >> 1)\n",
    "                    board.pop()\n",
    "            return r\n",
    "\n",
    "        dfs(0, 0, 0, 0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "#         def check(row, col, res, columns):\n",
    "#     if col in columns:\n",
    "#         return False\n",
    "\n",
    "#     for rr in range(row):\n",
    "#         delta = row - rr\n",
    "#         if col - delta >= 0 and res[rr][col - delta] == 'Q':\n",
    "#             return False\n",
    "\n",
    "#         if col + delta < len(res) and res[rr][col + delta] == 'Q':\n",
    "#             return False\n",
    "\n",
    "#     return True\n",
    "\n",
    "def check(row, col, res, columns):\n",
    "    if col in columns:\n",
    "        return False\n",
    "\n",
    "    for rr in range(row):\n",
    "        delta = row - rr\n",
    "        if col - delta >= 0 and res[rr][col - delta] == 'Q':\n",
    "            return False\n",
    "\n",
    "        if col + delta < len(res) and res[rr][col + delta] == 'Q':\n",
    "            return False\n",
    "\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        matrix = [['.' for _ in range(n)] for _ in range(n)]\n",
    "        result = []\n",
    "        columns = []\n",
    "\n",
    "        def dfs(row):\n",
    "            if row == len(matrix):\n",
    "                result.append([''.join(x) for x in matrix])\n",
    "\n",
    "            for cl in range(len(matrix)):\n",
    "                if check(row, cl, matrix, columns):\n",
    "                    matrix[row][cl] = 'Q'\n",
    "                    columns.append(cl)\n",
    "                    dfs(row + 1)\n",
    "                    matrix[row][cl] = '.'\n",
    "                    columns.remove(cl)\n",
    "        dfs(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        x = []\n",
    "        res = []\n",
    "        def place(self, k: int) ->bool:\n",
    "            for i in range(0, k):\n",
    "                if abs(k-i) == abs(x[k]-x[i]) or x[k] == x[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        def bfs(self, t: int):\n",
    "            if t >= n:\n",
    "                slt = []\n",
    "                for m in range(0, n):\n",
    "                    temp = ['.' for _ in range(0, n)]\n",
    "                    temp[x[m]] = 'Q'\n",
    "                    line = \"\".join(temp)\n",
    "                    slt.append(line)\n",
    "                res.append(slt)\n",
    "            else:\n",
    "                for j in range(0, n):\n",
    "                    x.append(j)\n",
    "                    if place(Solution, t):\n",
    "                        bfs(Solution, t + 1)\n",
    "                    x.pop()\n",
    "        bfs(Solution, 0)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        cols = set()\n",
    "        diag = set()\n",
    "        off_diag = set()\n",
    "        ans = []\n",
    "        def backtrack(i, tmp):\n",
    "            if i >= n:\n",
    "                ans.append(tmp)\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if j not in cols and (i-j) not in diag and (i + j) not in off_diag:\n",
    "                    cols.add(j)\n",
    "                    diag.add(i - j)\n",
    "                    off_diag.add(i + j)\n",
    "                    backtrack(i + 1, tmp + ['.' * j + 'Q' + '.' * (n - j - 1)])\n",
    "                    cols.remove(j)\n",
    "                    diag.remove(i - j)\n",
    "                    off_diag.remove(i+j)\n",
    "        backtrack(0, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        col = set()\n",
    "        left = set()\n",
    "        right = set()\n",
    "        ans = []\n",
    "        def queen(temp,i):\n",
    "            if i == n:\n",
    "                res = []\n",
    "                cur = ['.']*n\n",
    "                for index in temp:\n",
    "                    cur[index]='Q'\n",
    "                    res.append(''.join(cur))\n",
    "                    cur[index]='.'\n",
    "                ans.append(res)\n",
    "            for j in range(n):\n",
    "                if j not in col and i-j not in left and i+j not in right:\n",
    "                    col.add(j)\n",
    "                    left.add(i-j)\n",
    "                    right.add(i+j)\n",
    "                    queen(temp+[j],i+1)\n",
    "                    col.remove(j)\n",
    "                    left.remove(i-j)\n",
    "                    right.remove(i+j)\n",
    "        queen([],0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        # 用二维数组表示棋盘\n",
    "        bs = [[0] * n for _ in range(n)]\n",
    "\n",
    "        step = [[1, 0], [0, 1], [1, 1], [1, -1]]\n",
    "\n",
    "        # 设置棋盘值\n",
    "        def check_one(x, y):\n",
    "            if x < 0 or x == n or y < 0 or y == n:\n",
    "                # 棋盘外返回None\n",
    "                return None\n",
    "            return bs[x][y]\n",
    "\n",
    "        def check(x, y):\n",
    "            if bs[x][y]:\n",
    "                return False\n",
    "\n",
    "            for xo, yo in step:\n",
    "                i = 1\n",
    "                while 1:\n",
    "                    r = check_one(x + i * xo, y + i * yo)\n",
    "                    if r == None:\n",
    "                        break\n",
    "                    if r:\n",
    "                        return False\n",
    "                    i += 1\n",
    "\n",
    "                i = -1\n",
    "                while 1:\n",
    "                    r = check_one(x + i * xo, y + i * yo)\n",
    "                    if r == None:\n",
    "                        break\n",
    "                    if r:\n",
    "                        return False\n",
    "                    i -= 1\n",
    "\n",
    "            return True\n",
    "\n",
    "        # 按行依次增加Q\n",
    "        ret = []\n",
    "        now = [0] * n\n",
    "\n",
    "        def dfs(no):\n",
    "            x = no - 1\n",
    "            if x == n:\n",
    "                ret.append(now[:])\n",
    "                return\n",
    "\n",
    "            for y in range(n):\n",
    "                if check(x, y):\n",
    "                    bs[x][y] = 1\n",
    "                    now[x] = \".\" * y + \"Q\" + \".\" * (n - y - 1)\n",
    "                    dfs(no + 1)\n",
    "                    bs[x][y] = 0\n",
    "\n",
    "        dfs(1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def backtrack(row, state, n, diags1, diags2, cols, res):\n",
    "            if row == n:\n",
    "                res.append([''.join(list(r)) for r in state])\n",
    "                return \n",
    "            for col in range(n):\n",
    "                diag1 = row - col + n -1\n",
    "                diag2 = row + col\n",
    "                if not cols[col] and not diags1[diag1] and not diags2[diag2]:\n",
    "                    state[row][col] = 'Q'\n",
    "                    cols[col] = diags1[diag1] = diags2[diag2] = True\n",
    "                    backtrack(row+1, state, n, diags1, diags2, cols, res)\n",
    "                    state[row][col] = '.'\n",
    "                    cols[col] = diags1[diag1] = diags2[diag2] = False\n",
    "        state = [['.'] * n for _ in range(n)]\n",
    "        cols = [False] * n\n",
    "        diags1 = [False] * (2 * n - 1)\n",
    "        diags2 = [False] * (2 * n - 1)\n",
    "        res = []\n",
    "        backtrack(0, state, n, diags1, diags2, cols, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = []\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = 'Q'\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = '.'\n",
    "            return board\n",
    "        def backTrack(row):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backTrack(row+1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "\n",
    "        \n",
    "        \n",
    "        solutions = []\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        queens = [-1]*n\n",
    "        row = ['.']*n\n",
    "        backTrack(0)\n",
    "        return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = []\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def Print(pos,n):\n",
    "            a = [['.']*n for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                a[pos[i][0]][pos[i][1]] = 'Q'\n",
    "                a[i] = ''.join(a[i])\n",
    "            self.ans.append(a)\n",
    "        def check(x,y,col,dia1,dia2):\n",
    "            if col>>y&1 or dia1>>(x - y+n)&1 or dia2>>(x + y)&1:\n",
    "                return False\n",
    "            return True\n",
    "        def dfs(num, pre,n,col,dia1,dia2):\n",
    "            if num == n:\n",
    "                Print(pre,n)\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if check(num,i,col,dia1,dia2):\n",
    "                    col^=1<<i\n",
    "                    dia1^=1<<(n+num-i)\n",
    "                    dia2^=1<<(num+i)\n",
    "                    dfs(num+1,pre+[[num,i]],n,col,dia1,dia2)\n",
    "                    col^=1<<i\n",
    "                    dia1^=1<<(n+num-i)\n",
    "                    dia2^=1<<(num+i)\n",
    "        \n",
    "        dfs(0,[],n,0,0,0)\n",
    "        return self.ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        chessboard = [['.']*n for _ in range(n)]\n",
    "        res = []\n",
    "        def isValid(row, col):\n",
    "            for i in range(row):\n",
    "                if chessboard[i][col] == 'Q': return False\n",
    "            i, j = row-1, col-1\n",
    "            while i >= 0 and j >= 0:\n",
    "                if chessboard[i][j] == 'Q':\n",
    "                    return False\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            i,j = row-1, col+1\n",
    "            while i >= 0 and j < n:\n",
    "                if chessboard[i][j] == 'Q':\n",
    "                    return False\n",
    "                i -= 1\n",
    "                j += 1\n",
    "            return True\n",
    "        def backtracking(row):\n",
    "            if row == n:\n",
    "                pth = []\n",
    "                for x in chessboard:\n",
    "                    pth.append(''.join(x))\n",
    "                res.append(pth)\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if isValid(row, j):\n",
    "                    chessboard[row][j] = 'Q'\n",
    "                    backtracking(row + 1)\n",
    "                    chessboard[row][j] = '.'\n",
    "        backtracking(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        self.n = n \n",
    "        self.ans = []\n",
    "        board = [['.'] * n for _ in range(n)]\n",
    "        used = set([])\n",
    "        self.backtrack(0, board, used)\n",
    "        return self.ans\n",
    "\n",
    "    def backtrack(self, pos: int, board: List[List[str]], used: set):\n",
    "        if pos == self.n:\n",
    "            res = []\n",
    "            for each in board:\n",
    "                res.append(''.join(each))\n",
    "            self.ans.append(res)\n",
    "            return\n",
    "        for i in range(self.n):\n",
    "            row = str(i) + 'r'\n",
    "            dial1 = str(i - pos) + 'd'\n",
    "            dial2 = str(i + pos) + 's'\n",
    "            if row not in used and dial1 not in used and dial2 not in used:\n",
    "                board[i][pos] = 'Q'\n",
    "                used.add(row)\n",
    "                used.add(dial1)\n",
    "                used.add(dial2)\n",
    "                self.backtrack(pos + 1, board, used)\n",
    "                board[i][pos] = '.'\n",
    "                used.remove(row)\n",
    "                used.remove(dial1)\n",
    "                used.remove(dial2)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        if not n: return []\n",
    "        board=[['.']*n for _ in range(n)]\n",
    "        res=[]\n",
    "        def isValid(board,row:int,col:int):\n",
    "            # 检查同一列\n",
    "            for i in range(n):\n",
    "                if board[i][col]=='Q':\n",
    "                    return False\n",
    "            # 判断左上角是否冲突\n",
    "            i,j=row-1,col-1\n",
    "            while i>=0 and j>=0:\n",
    "                if board[i][j]=='Q':\n",
    "                    return False \n",
    "                i,j=i-1,j-1\n",
    "            # 判断右上角是否冲突\n",
    "            i,j=row-1,col+1\n",
    "            while i>=0 and j<n:\n",
    "                if board[i][j]=='Q':\n",
    "                    return False\n",
    "                i,j=i-1,j+1\n",
    "            return True\n",
    "        def dfs(board,row,n):\n",
    "            if row==n:\n",
    "                tmp=[]\n",
    "                for line in board:\n",
    "                    tmp.append(''.join(line))\n",
    "                res.append(tmp)\n",
    "                return \n",
    "            for col in range(n):\n",
    "                if not isValid(board,row,col):\n",
    "                    continue\n",
    "                board[row][col]='Q'\n",
    "                dfs(board,row+1,n) \n",
    "                board[row][col]='.'\n",
    "        dfs(board,0,n) \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        self.ans = []\n",
    "\n",
    "        board = [[\".\"] * n for _ in range(n)]\n",
    "        \n",
    "        self.backtrack(board, 0)\n",
    "        return self.ans\n",
    "\n",
    "    def backtrack(self, board, row):\n",
    "        if row == len(board):\n",
    "            self.ans.append([''.join(board[i]) for i in range(row)])\n",
    "            return \n",
    "        \n",
    "        n = len(board[row])\n",
    "        for col in range(n):\n",
    "            if not self.isValid(board, row, col):\n",
    "                continue\n",
    "            \n",
    "            board[row][col] = \"Q\"\n",
    "            self.backtrack(board, row+1)\n",
    "            board[row][col] = \".\"\n",
    "    \n",
    "            \n",
    "    \n",
    "    def isValid(self, board, row, col):\n",
    "        n = len(board)\n",
    "        for i in range(n):\n",
    "            if board[i][col] == \"Q\":\n",
    "                return False\n",
    "\n",
    "        r, c = row -1, col + 1\n",
    "        while r >= 0 and c < n:\n",
    "            if board[r][c] == \"Q\":\n",
    "                return False\n",
    "            \n",
    "            r -= 1\n",
    "            c += 1\n",
    "        # 左上方\n",
    "        r, c = row -1, col -1\n",
    "        while r >= 0 and c >= 0:\n",
    "            if board[r][c] == \"Q\":\n",
    "                return False\n",
    "            r -= 1\n",
    "            c -=1\n",
    "        return True\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        st = [['.' for i in range(n)] for j in range(n)]\n",
    "        res = []\n",
    "        def dfs(x_d, y_d, cur):\n",
    "            j = len(cur)\n",
    "            if len(cur) == n:\n",
    "                m = []\n",
    "                for i in st: m.append(''.join(i))\n",
    "                res.append(m)\n",
    "            for i in range(n):\n",
    "                if i not in cur and i + j not in x_d and i-j not in y_d:\n",
    "                    st[j][i] = 'Q'\n",
    "                    dfs(x_d+[i+j],y_d+[i-j],cur+[i])\n",
    "                    st[j][i] = '.'\n",
    "        dfs([], [], [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        ans = []\n",
    "        res = [['.']*n for _ in range(n)]\n",
    "        left = set()\n",
    "        right = set()\n",
    "        col = set()\n",
    "        def dfs(temp,i):\n",
    "            if i == n:\n",
    "                res = [['.']*n for _ in range(n)]\n",
    "                for j in range(n):\n",
    "                    res[j][temp[j]] = 'Q'\n",
    "                ans.append([''.join(cur) for cur in res])\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if j not in col and i+j not in left and i-j not in right:\n",
    "                    col.add(j)\n",
    "                    left.add(i+j)\n",
    "                    right.add(i-j)\n",
    "                    dfs(temp+[j],i+1)\n",
    "                    col.discard(j)\n",
    "                    left.discard(i+j)\n",
    "                    right.discard(i-j)\n",
    "            return\n",
    "        dfs([],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        st = [['.'for i in range(n) ] for j in range(n)]\n",
    "        res =  []\n",
    "        def dfs (x_d,y_d,cur):\n",
    "            j = len(cur)\n",
    "            if j == n:\n",
    "                m = []\n",
    "                for i in st:\n",
    "                    m.append(''.join(i))\n",
    "                res.append(m)\n",
    "            \n",
    "            for i in range(n):\n",
    "                if i not in cur and i + j not in x_d and j - i not in y_d:\n",
    "                    st[j][i] ='Q'\n",
    "                    dfs(x_d + [i+j],y_d+[j - i],cur + [i])\n",
    "                    st[j][i]='.'\n",
    "        dfs([],[],[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def dfs(i,path,total,re):\n",
    "            if i>n:\n",
    "                re.append(path)\n",
    "                return\n",
    "            for j in range(n):\n",
    "                acc = 1<<j\n",
    "                if acc&total:continue\n",
    "                flag = True\n",
    "                for k in range(1,i):\n",
    "                    tmpl, tmpr = acc<<k,acc>>k\n",
    "                    if tmpl&path[-k] or tmpr&path[-k]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    dfs(i+1,path+[acc],total|acc,re)\n",
    "        re = []\n",
    "        dfs(1,[],0,re)\n",
    "        ans = []\n",
    "        for re0 in re:\n",
    "            res = []\n",
    "            for c in re0:\n",
    "                res.append(bin(c)[2:].replace('0','.',n-1).replace('1','Q').rjust(n,'.'))\n",
    "            ans.append(res)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generate():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row = [\".\"] * n\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "            return board\n",
    "\n",
    "        def backtrack(row):\n",
    "            if row == n:\n",
    "                board = generate()\n",
    "                print(board)\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in dig1s or row + i in dig2s:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    dig1s.add(row - i)\n",
    "                    dig2s.add(row + i)\n",
    "\n",
    "                    backtrack(row + 1)\n",
    "\n",
    "                    columns.remove(i)\n",
    "                    dig1s.remove(row - i)\n",
    "                    dig2s.remove(row + i)\n",
    "        \n",
    "\n",
    "        solutions = []\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        dig1s = set()\n",
    "        dig2s = set()\n",
    "\n",
    "        backtrack(0)\n",
    "        return solutions\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        mat = [['.'] * n for _ in range(n)]\n",
    "        \n",
    "        def backtracing(mat, res, cur_row):\n",
    "            if cur_row == n:\n",
    "                res.append([''.join(line) for line in mat])\n",
    "                return \n",
    "\n",
    "            for col in range(n):\n",
    "                # print(mat, self.isValid(cur_row, col, n, mat))\n",
    "                if self.isValid(cur_row, col, n, mat) == True:\n",
    "                    mat[cur_row][col] = 'Q' \n",
    "                    backtracing(mat, res, cur_row + 1)\n",
    "                    mat[cur_row][col] = '.'\n",
    "        \n",
    "        res = []\n",
    "        backtracing(mat, res, 0)\n",
    "        # print(res) \n",
    "        return res \n",
    "    \n",
    "    def isValid(self, x, y, n, mat) -> bool:\n",
    "        row = x\n",
    "        for col in range(n):\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "        \n",
    "        col = y \n",
    "        for row in range(n):\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "        \n",
    "        row = x\n",
    "        col = y\n",
    "        while row >= 0 and col >= 0 and row < n and col < n:\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "            row -= 1\n",
    "            col -= 1\n",
    "\n",
    "        row = x\n",
    "        col = y\n",
    "        while row >= 0 and col >= 0 and row < n and col < n:\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "            row -= 1\n",
    "            col += 1\n",
    "\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "\n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        st = [['.' for j in range(n)] for i in range(n)]\n",
    "        res = []\n",
    "        def dfs(x_d, y_d, cur):\n",
    "            i = len(cur)\n",
    "            if len(cur) == n:\n",
    "                m = []\n",
    "                for row in st: m.append(''.join(row))\n",
    "                res.append(m)\n",
    "            for j in range(n):\n",
    "                if j not in cur and j + i not in x_d and j-i not in y_d:\n",
    "                    st[i][j] = 'Q'\n",
    "                    dfs(x_d+[j+i],y_d+[j-i],cur+[j])\n",
    "                    st[i][j] = '.'\n",
    "        dfs([], [], [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def printArr(self,arr): #打印矩阵\n",
    "        for x in range(0,N):\n",
    "            for y in range(0,N):\n",
    "                print(arr[x][y],end=\" \")\n",
    "            print()\n",
    "\n",
    "    def isValid(self,arr, x, y): # 判断是否合法\n",
    "    #    for i in range(0, N):\n",
    "    #        if (arr[x][i] == 1 or arr[i][y] == 1): #十字方向\n",
    "    #            return False\n",
    "        for i, j in zip(range(x, -1, -1), range(y, -1, -1)):#从x,y向左上角斜线方向找1\n",
    "            if (arr[i][j] == 'Q'):\n",
    "                return False\n",
    "        for i, j in zip(range(x, -1, -1), range(y, self.N)):#从x,y向右上角斜线方向找1\n",
    "            if (arr[i][j] == 'Q'):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self,arr,row,res):\n",
    "\n",
    "        if row ==self.N:  #走到最后一行如果存在则return\n",
    "            #print(count)\n",
    "            # count+=1\n",
    "            #printArr(arr)\n",
    "            res.append(copy.deepcopy(arr))\n",
    "            return\n",
    "        for i in range(0,self.N):\n",
    "            if  (self.bit& 1<<i):\n",
    "                continue\n",
    "            if self.isValid(arr,row,i):\n",
    "                self.bit |= (1<<i) # 第n位置位1  （将一整个数组所有列视为一行 \n",
    "                arr[row]=\".\"*(i)+\"Q\"+\".\"*(self.N-i-1) #给i行 row列置位1\n",
    "                self.dfs(arr,row+1,res)  #递归进入下一行\n",
    "                self.bit &= ~(1<<i)# 第n位置位0\n",
    "                arr[row]=\".\"*self.N  #给i行 row列回溯0\n",
    "                \n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        res= []\n",
    "        arr = [\".\"*n for _ in range(n)]\n",
    "        self.N=n\n",
    "        self.bit=0b00000000\n",
    "        \n",
    "        self.dfs(arr,0,res)\n",
    "\n",
    "        return res\n",
    "\n",
    "    N=0\n",
    "    bit=0b00000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def isValid(path, i, j):\n",
    "            nonlocal n\n",
    "            for row in range(i):\n",
    "                if path[row][j] == 'Q':\n",
    "                    return False\n",
    "            row, col = i - 1, j - 1\n",
    "            while row >= 0 and col >= 0:\n",
    "                if path[row][col] == 'Q':\n",
    "                    return False\n",
    "                row -= 1\n",
    "                col -= 1\n",
    "            row, col = i - 1, j + 1\n",
    "            while row >= 0 and col < n:\n",
    "                if path[row][col] == 'Q':\n",
    "                    return False\n",
    "                row -= 1\n",
    "                col += 1\n",
    "            return True\n",
    "\n",
    "        def backtrack(start):\n",
    "            nonlocal n\n",
    "            if start == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if not isValid(path, start, i):\n",
    "                    continue\n",
    "                tmp = ['.'] * n\n",
    "                tmp[i] = 'Q'\n",
    "                path.append(''.join(tmp))\n",
    "                backtrack(start + 1)\n",
    "                path.pop()\n",
    "        backtrack(0)\n",
    "        return res\n",
    "\n",
    "        backtrack(n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def dfs(i,path,total,re):\n",
    "            if i>n:\n",
    "                re.append(path)\n",
    "                return\n",
    "            for j in range(n):\n",
    "                acc = 1<<j\n",
    "                if acc&total:continue\n",
    "                flag = True\n",
    "                for k in range(1,i):\n",
    "                    tmpl, tmpr = acc<<k,acc>>k\n",
    "                    if tmpl&path[-k] or tmpr&path[-k]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    dfs(i+1,path+[acc],total|acc,re)\n",
    "        re = []\n",
    "        dfs(1,[],0,re)\n",
    "        ans = []\n",
    "        for re0 in re:\n",
    "            res = []\n",
    "            for c in re0:\n",
    "                tmp = ''\n",
    "                for i in range(n):\n",
    "                    if (c>>i)&1==1:\n",
    "                        tmp+='Q'\n",
    "                    else:\n",
    "                        tmp+='.'\n",
    "                res.append(tmp)\n",
    "            ans.append(res)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateboard():\n",
    "            board=list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]]=\"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]]=\".\"\n",
    "            return board\n",
    "        def backtrack(row):\n",
    "            if row==n:\n",
    "                board=generateboard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row-i in diagonal1 or row+i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row]=i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row-i)\n",
    "                    diagonal2.add(row+i)\n",
    "                    backtrack(row+1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row-i)\n",
    "                    diagonal2.remove(row+i)\n",
    "        solutions=list()\n",
    "        queens=[-1]*n\n",
    "        columns=set()\n",
    "        diagonal1=set()\n",
    "        diagonal2=set()\n",
    "        row=[\".\"]*n\n",
    "        backtrack(0)\n",
    "        return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def dfs(i,path,total,re):\n",
    "            if i>n:\n",
    "                re.append(path)\n",
    "                return\n",
    "            for j in range(n):\n",
    "                acc = 1<<j\n",
    "                if acc&total:continue\n",
    "                flag = True\n",
    "                for k in range(1,i):\n",
    "                    tmpl, tmpr = acc<<k,acc>>k\n",
    "                    if tmpl&path[-k] or tmpr&path[-k]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    dfs(i+1,path+[acc],total|acc,re)\n",
    "        re = []\n",
    "        dfs(1,[],0,re)\n",
    "        ans = []\n",
    "        for re0 in re:\n",
    "            res = []\n",
    "            for c in re0:\n",
    "                res.append(bin(c)[2:].replace('0','.',n-1).replace('1','Q').rjust(n,'.'))\n",
    "            ans.append(res)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "                    \n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        ans = []\n",
    "        col = [0]*n\n",
    "        m = 2*n-1\n",
    "        diag1 = [False]*m\n",
    "        diag2 = [False]*m\n",
    "        on_path = [False]*n\n",
    "\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                ans.append(['.'*c+'Q'+'.'*(n-c-1) for c in col])\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if not on_path[j] and not diag1[i+j] and not diag2[i-j]:\n",
    "                    col[i]=j\n",
    "                    on_path[j]=diag1[i+j]=diag2[i-j]=True\n",
    "                    dfs(i+1)\n",
    "                    on_path[j]=diag1[i+j]=diag2[i-j]=False\n",
    "        dfs(0)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def printArr(self,arr): #打印矩阵\n",
    "        for x in range(0,N):\n",
    "            for y in range(0,N):\n",
    "                print(arr[x][y],end=\" \")\n",
    "            print()\n",
    "\n",
    "    def isValid(self,arr, x, y): # 判断是否合法\n",
    "        for i in range(0, self.N):\n",
    "            if (arr[x][i] == 'Q' or arr[i][y] =='Q'): #十字方向\n",
    "                return False\n",
    "        for i, j in zip(range(x, -1, -1), range(y, -1, -1)):#从x,y向左上角斜线方向找1\n",
    "            if (arr[i][j] == 'Q'):\n",
    "                return False\n",
    "        for i, j in zip(range(x, -1, -1), range(y, self.N)):#从x,y向右上角斜线方向找1\n",
    "            if (arr[i][j] == 'Q'):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self,arr,row,res):\n",
    "\n",
    "        if row ==self.N:  #走到最后一行如果存在则return\n",
    "            #print(count)\n",
    "            # count+=1\n",
    "            #printArr(arr)\n",
    "            res.append(copy.deepcopy(arr))\n",
    "            return\n",
    "        for i in range(0,self.N):\n",
    "            if  (self.bit& 1<<i):\n",
    "                continue\n",
    "            if self.isValid(arr,row,i):\n",
    "               # self.bit |= (1<<i) # 第n位置位1  （将一整个数组所有列视为一行 \n",
    "                arr[row]=\".\"*(i)+\"Q\"+\".\"*(self.N-i-1) #给i行 row列置位1\n",
    "                self.dfs(arr,row+1,res)  #递归进入下一行\n",
    "               # self.bit &= ~(1<<i)# 第n位置位0\n",
    "                arr[row]=\".\"*self.N  #给i行 row列回溯0\n",
    "                \n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        res= []\n",
    "        arr = [\".\"*n for _ in range(n)]\n",
    "        self.N=n\n",
    "        #self.bit=0b00000000\n",
    "        \n",
    "        self.dfs(arr,0,res)\n",
    "\n",
    "        return res\n",
    "\n",
    "    N=0\n",
    "    bit=0b00000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        columns=set()\n",
    "        diag_right=set()\n",
    "        diag_left=set()\n",
    "        queens=[-1]*n\n",
    "        res=[]\n",
    "        row_str=[\".\"]*n\n",
    "\n",
    "        def GenerateBoard():\n",
    "            board=[]\n",
    "            for i  in range(n):\n",
    "                row_str[queens[i]]=\"Q\"\n",
    "                board.append(\"\".join(row_str))\n",
    "                row_str[queens[i]]=\".\"\n",
    "            res.append(board)\n",
    "\n",
    "        def helper(row):\n",
    "            if row==n:\n",
    "                GenerateBoard()\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if i in columns or row-i in diag_right or row+i in diag_left:\n",
    "                    continue\n",
    "                queens[row]=i\n",
    "                columns.add(i)\n",
    "                diag_right.add(row-i)\n",
    "                diag_left.add(row+i)\n",
    "                helper(row+1)\n",
    "                columns.remove(i)\n",
    "                diag_right.remove(row-i)\n",
    "                diag_left.remove(row+i)\n",
    "        helper(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        records = [['.'] * n for i in range(n)]\n",
    "        res = []\n",
    "        \n",
    "        def dfs(angle_1, angle_2, cur):\n",
    "            i = len(cur)\n",
    "            if i == n:\n",
    "                tmp = []\n",
    "                for record in records:\n",
    "                    tmp.append(''.join(record))\n",
    "                res.append(tmp[:])\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if i + j not in angle_1 and i - j not in angle_2 and j not in cur:\n",
    "                    records[i][j] = 'Q'\n",
    "                    dfs(angle_1+[i+j], angle_2+[i-j], cur+[j])\n",
    "                    records[i][j] = '.'\n",
    "            \n",
    "        dfs([], [], [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        self.n = n\n",
    "        self.col = [False for i in range(n)]\n",
    "        self.gx = [False for i in range(n + n)]\n",
    "        self.gfx=  [False for i in range(n + n)]\n",
    "        self.g = [['.' for i in range(n)] for j in range(n)]\n",
    "        self.res = []\n",
    "        self.dfs(0)\n",
    "        return self.res\n",
    "    def dfs(self, c):\n",
    "        if c == self.n:\n",
    "            t = []\n",
    "            for i in range(self.n):\n",
    "                t.append(''.join(self.g[i]))\n",
    "            self.res.append(t)\n",
    "            return\n",
    "        for i in range(self.n):\n",
    "            if (not self.col[i]) and (not self.gx[i - c + self.n] and (not self.gfx[i + c])):\n",
    "                self.g[c][i] = 'Q'\n",
    "                self.col[i] = self.gx[i - c + self.n] = self.gfx[i + c] = True\n",
    "                self.dfs(c + 1)\n",
    "                self.g[c][i] = '.'\n",
    "                self.col[i] = self.gx[i - c + self.n] = self.gfx[i + c] = False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        \n",
    "        def traversal(col_state,before_queens):\n",
    "            # print(\" \"*len(before_queens),col_state, before_queens)\n",
    "            if len(before_queens)==n:\n",
    "                return [before_queens]\n",
    "            new_row = [\".\"]*n\n",
    "\n",
    "            cur_i = len(before_queens)\n",
    "            result_list = []\n",
    "            for j in range(n):\n",
    "                if col_state[j]:\n",
    "                    for k in range(len(before_queens)):\n",
    "                        if abs(k-cur_i)==abs(before_queens[k]-j):\n",
    "                            break\n",
    "                    else:\n",
    "                        col_state[j] = False\n",
    "                        result_list.extend(traversal(col_state, before_queens+[j]))\n",
    "                        col_state[j] = True\n",
    "            # print(\" \"*len(before_queens), result_list)\n",
    "            return result_list\n",
    "        \n",
    "        return [[\"\".join(\"Q\" if j==cur_result[i] else \".\"  for j in range(n)) for i in range(n)] for cur_result in traversal([True]*n, [])]\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        # 回溯=DFS+剪枝优化\n",
    "        def dfs(i:int,record1:List[int],record2:List[int],record3:List[int]):# 递归到第i行，record分别记录横向，一三角分线、二四角分线\n",
    "            if i==n:\n",
    "                temp=['.'*n]*n\n",
    "                for m,j in enumerate(record1):\n",
    "                    temp[m]=temp[m][:j]+'Q'+temp[m][j+1:]\n",
    "                nonlocal ans\n",
    "                ans.append(temp)\n",
    "            for k in range(n):\n",
    "                if k not in record1 and (i-k) not in record2 and (i+k) not in record3:\n",
    "                    dfs(i+1,record1+[k],record2+[i-k],record3+[i+k])\n",
    "        ans=[]\n",
    "        dfs(0,[],[],[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res: List[List[str]] = []\n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        board: List[List[str]] = [[\".\"] * n for i in range(n)]\n",
    "        self.recur(n, board, 0)\n",
    "        return self.res\n",
    "    \n",
    "    def recur(self, n: int, board: List[List[str]], row: int):\n",
    "        if (row == n):\n",
    "            # way1\n",
    "            # result: List[str] = []\n",
    "            # for i in range(0, n):\n",
    "            #     line: str = \"\"\n",
    "            #     for j in range(0, n):\n",
    "            #         line += board[i][j]\n",
    "            #     result.append(line)\n",
    "\n",
    "            # way2\n",
    "            # [result.append(\"\".join(board[i])) for i in range(n)]\n",
    "\n",
    "            # way3\n",
    "            result = [\"\".join(board[i]) for i in range(n)]\n",
    "            self.res.append(result)\n",
    "            return\n",
    "        \n",
    "        # 遍历每一列\n",
    "        for col in range(0, n):\n",
    "            if (self.valid(board, n, row, col)):\n",
    "                board[row][col] = 'Q'\n",
    "                self.recur(n, board, row + 1)\n",
    "                board[row][col] = '.'\n",
    "\n",
    "    def valid(self, board: List[List[str]], n: int, row: int, col: int):\n",
    "        # 扫描上方\n",
    "        for i in range(row - 1, -1, -1):\n",
    "            if (board[i][col] == 'Q'):\n",
    "                return False\n",
    "\n",
    "        # 扫描左上\n",
    "        i = row - 1; j = col - 1\n",
    "        while (i >= 0 and j >= 0):\n",
    "            if (board[i][j] == 'Q'):\n",
    "                return False\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "        # 扫描右上\n",
    "        i = row - 1; j = col + 1\n",
    "        while (i >= 0 and j < n):\n",
    "            if (board[i][j] == 'Q'):\n",
    "                return False\n",
    "            i -= 1\n",
    "            j += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "                    \n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "#         def check(row, col, res, columns):\n",
    "#     if col in columns:\n",
    "#         return False\n",
    "\n",
    "#     for rr in range(row):\n",
    "#         delta = row - rr\n",
    "#         if col - delta >= 0 and res[rr][col - delta] == 'Q':\n",
    "#             return False\n",
    "\n",
    "#         if col + delta < len(res) and res[rr][col + delta] == 'Q':\n",
    "#             return False\n",
    "\n",
    "#     return True\n",
    "\n",
    "def check(row, col, res, columns):\n",
    "    if col in columns:\n",
    "        return False\n",
    "\n",
    "    for rr in range(row):\n",
    "        delta = row - rr\n",
    "        if col - delta >= 0 and res[rr][col - delta] == 'Q':\n",
    "            return False\n",
    "\n",
    "        if col + delta < len(res) and res[rr][col + delta] == 'Q':\n",
    "            return False\n",
    "\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        matrix = [['.' for _ in range(n)] for _ in range(n)]\n",
    "        result = []\n",
    "        columns = []\n",
    "\n",
    "        def dfs(row):\n",
    "            if row == len(matrix):\n",
    "                result.append([''.join(x) for x in matrix])\n",
    "\n",
    "            for cl in range(len(matrix)):\n",
    "                if check(row, cl, matrix, columns):\n",
    "                    matrix[row][cl] = 'Q'\n",
    "                    columns.append(cl)\n",
    "                    dfs(row + 1)\n",
    "                    matrix[row][cl] = '.'\n",
    "                    columns.remove(cl)\n",
    "        dfs(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        columns=set()\n",
    "        diag_right=set()\n",
    "        diag_left=set()\n",
    "        queens=[-1]*n\n",
    "        res=[]\n",
    "        row_str=[\".\"]*n\n",
    "\n",
    "        def GenerateBoard():\n",
    "            board=[]\n",
    "            for i  in range(n):\n",
    "                row_str[queens[i]]=\"Q\"\n",
    "                board.append(\"\".join(row_str))\n",
    "                row_str[queens[i]]=\".\"\n",
    "            res.append(board)\n",
    "\n",
    "        def helper(row):\n",
    "            if row==n:\n",
    "                GenerateBoard()\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if i in columns or row-i in diag_right or row+i in diag_left:\n",
    "                    continue\n",
    "                queens[row]=i\n",
    "                columns.add(i)\n",
    "                diag_right.add(row-i)\n",
    "                diag_left.add(row+i)\n",
    "                helper(row+1)\n",
    "                columns.remove(i)\n",
    "                diag_right.remove(row-i)\n",
    "                diag_left.remove(row+i)\n",
    "        helper(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        res = []\n",
    "        s = \".\" * n\n",
    "        def backtrack(i, tmp, col, z_diagonal, f_diagonal):\n",
    "            if i == n:\n",
    "                res.append(tmp)\n",
    "                return \n",
    "            for j in range(n):\n",
    "                if j not in col and i + j not in z_diagonal and i - j not in f_diagonal:\n",
    "                    backtrack(i+1, tmp + [s[:j] + \"Q\" + s[j+1:]], col | {j}, z_diagonal | {i + j} , f_diagonal | {i - j}) \n",
    "            \n",
    "        backtrack(0, [], set(), set(), set())    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            nonlocal row\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = 'Q'\n",
    "                board.append(''.join(row))\n",
    "                row[queens[i]] = '.'\n",
    "            return board\n",
    "\n",
    "        def backTrack(r):\n",
    "            if r == n:\n",
    "                board = generateBoard()\n",
    "                ans.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or r - i in diagonal1 or r + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[r] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(r - i)\n",
    "                    diagonal2.add(r + i)\n",
    "                    backTrack(r + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(r - i)\n",
    "                    diagonal2.remove(r + i)\n",
    "\n",
    "        ans = []\n",
    "        queens = [-1] * n\n",
    "        columns, diagonal1, diagonal2 = set(), set(), set()\n",
    "        row = ['.'] * n\n",
    "        backTrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "                    \n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        st = [['.'for i in range(n) ] for j in range(n)]\n",
    "        res =  []\n",
    "        def dfs (x_d,y_d,cur):\n",
    "            j = len(cur)\n",
    "            if j == n:\n",
    "                m = []\n",
    "                for i in st:\n",
    "                    m.append(''.join(i))\n",
    "                res.append(m)\n",
    "            \n",
    "            for i in range(n):\n",
    "                if i not in cur and i + j not in x_d and i -j not in y_d:\n",
    "                    st[j][i] ='Q'\n",
    "                    dfs(x_d + [i+j],y_d+[i-j],cur + [i])\n",
    "                    st[j][i]='.'\n",
    "        dfs([],[],[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "                    \n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def position(col, row, n):\n",
    "            if row == n:\n",
    "                printSolution(col, n)\n",
    "                return\n",
    "\n",
    "            for row_position in range(n):\n",
    "                col[row] = row_position\n",
    "                if isValid(col, row):\n",
    "                    position(col, row + 1, n)\n",
    "\n",
    "        def isValid(col, row):\n",
    "            if len(set(col[:row + 1])) != len(col[:row + 1]):\n",
    "                return False\n",
    "\n",
    "            for i in range(row):\n",
    "                if abs(col[i] - col[row]) == int(row - i):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def printSolution(col, n):\n",
    "            ans = []\n",
    "            for row in range(n):\n",
    "                line = \"\"\n",
    "                for column in range(n):\n",
    "                    if col[row] == column:\n",
    "                        line += \"Q\"\n",
    "                    else:\n",
    "                        line += \".\"\n",
    "                ans.append(line)\n",
    "            result.append(ans)\n",
    "\n",
    "\n",
    "        result = []\n",
    "        position([-1] * n, 0, n)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        r_dic,c_dic = defaultdict(bool),defaultdict(bool)\n",
    "        q_dic,p_dic = defaultdict(bool),defaultdict(bool)\n",
    "        grid = [['.']*n for _ in range(n)]\n",
    "        ans = []\n",
    "        def dfs(r,c,cnt):\n",
    "            if r == n:\n",
    "                if cnt == n:\n",
    "                    stack = [''.join(s) for s in grid]\n",
    "                    ans.append(stack)\n",
    "                return\n",
    "            if c == n:\n",
    "                if r_dic[r]:\n",
    "                    dfs(r+1,0,cnt)\n",
    "                return\n",
    "            if r_dic[r] or c_dic[c] or q_dic[r-c] or p_dic[r+c]:\n",
    "                dfs(r,c+1,cnt)\n",
    "                return\n",
    "            for x in 'Q.':\n",
    "                if x == 'Q':\n",
    "                    r_dic[r] = True\n",
    "                    c_dic[c] = True\n",
    "                    q_dic[r-c] = True\n",
    "                    p_dic[r+c] = True\n",
    "                    grid[r][c] = x\n",
    "                    dfs(r,c+1,cnt+1)\n",
    "                    grid[r][c] = '.'\n",
    "                    r_dic[r] = False\n",
    "                    c_dic[c] = False\n",
    "                    q_dic[r-c] = False\n",
    "                    p_dic[r+c] = False\n",
    "                else:\n",
    "                    dfs(r,c+1,cnt)\n",
    "        dfs(0,0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def could_place(row, col):\n",
    "            # 检查列\n",
    "            for prev_row in range(row):\n",
    "                if board[prev_row] == col or \\\n",
    "                    board[prev_row] - prev_row == col - row or \\\n",
    "                    board[prev_row] + prev_row == col + row:\n",
    "                    return False\n",
    "            return True\n",
    "            \n",
    "        def place_queen(n, row):\n",
    "            if row == n:\n",
    "                output.append(board[:])\n",
    "                return\n",
    "            for col in range(n):\n",
    "                if could_place(row, col):\n",
    "                    board[row] = col\n",
    "                    place_queen(n, row + 1)\n",
    "                    board[row] = 0\n",
    "                    \n",
    "        def board_to_result(board):\n",
    "            res = []\n",
    "            for i in range(n):\n",
    "                res.append(\".\" * board[i] + \"Q\" + \".\" * (n - board[i] - 1))\n",
    "            return res\n",
    "        \n",
    "        board = [0] * n\n",
    "        output = []\n",
    "        place_queen(n, 0)\n",
    "        \n",
    "        return [board_to_result(b) for b in output]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        rlist = []\n",
    "        cols = []\n",
    "        diag1 = []\n",
    "        diag2 = []\n",
    "        queens = [-1] * n\n",
    "\n",
    "        def get_result():\n",
    "            x = []\n",
    "            for q in queens:\n",
    "                xx = ['.']*n\n",
    "                xx[q] = 'Q'\n",
    "                x.append(''.join(xx))\n",
    "            return x\n",
    "\n",
    "        def dfs(row):\n",
    "            if row==n:\n",
    "                y = get_result()\n",
    "                rlist.append(y)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in cols:\n",
    "                        continue\n",
    "                    if row+i in diag1:\n",
    "                        continue\n",
    "                    if row-i in diag2:\n",
    "                        continue\n",
    "                    cols.append(i)\n",
    "                    diag1.append(row+i)\n",
    "                    diag2.append(row-i)\n",
    "                    queens[row] = i\n",
    "                    dfs(row+1)\n",
    "                    cols.remove(i)\n",
    "                    diag1.remove(row+i)\n",
    "                    diag2.remove(row-i)\n",
    "\n",
    "        dfs(0)\n",
    "        return rlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def is_not_under_attack(row, col):\n",
    "            for prev_row in range(row):\n",
    "                if board[prev_row] == col or \\\n",
    "                    board[prev_row] - prev_row == col - row or \\\n",
    "                    board[prev_row] + prev_row == col + row:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def place_queen(n, row):\n",
    "            if row == n:\n",
    "                output.append(board[:])\n",
    "                return\n",
    "            for col in range(n):\n",
    "                if is_not_under_attack(row, col):\n",
    "                    board[row] = col\n",
    "                    place_queen(n, row + 1)\n",
    "                    board[row] = 0\n",
    "\n",
    "        def board_to_result(board):\n",
    "            res = []\n",
    "            for row in board:\n",
    "                res.append('.' * row + 'Q' + '.' * (n - row - 1))\n",
    "            return res\n",
    "\n",
    "        output = []\n",
    "        board = [0] * n\n",
    "        place_queen(n, 0)\n",
    "        return [board_to_result(board) for board in output]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res: List[List[str]] = []\n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        board: List[List[str]] = []\n",
    "        for i in range(n):\n",
    "            board.append([\".\"] * n)\n",
    "        self.recur(n, board, 0)\n",
    "        return self.res\n",
    "    \n",
    "    def recur(self, n: int, board: List[List[str]], row: int):\n",
    "        if (row == n):\n",
    "            print(f\"here1. row: {row}\")\n",
    "            result: List[str] = []\n",
    "            for i in range(0, n):\n",
    "                line: str = \"\"\n",
    "                for j in range(0, n):\n",
    "                    line += board[i][j]\n",
    "                result.append(line)\n",
    "            self.res.append(result)\n",
    "            return\n",
    "        \n",
    "        # 遍历每一列\n",
    "        for col in range(0, n):\n",
    "            if (self.valid(board, n, row, col)):\n",
    "                board[row][col] = 'Q'\n",
    "                self.recur(n, board, row + 1)\n",
    "                board[row][col] = '.'\n",
    "\n",
    "    def valid(self, board: List[List[str]], n: int, row: int, col: int):\n",
    "        # 扫描上方\n",
    "        for i in range(row - 1, -1, -1):\n",
    "            if (board[i][col] == 'Q'):\n",
    "                return False\n",
    "\n",
    "        # 扫描左上\n",
    "        i = row - 1\n",
    "        j = col - 1\n",
    "        while (i >= 0 and j >= 0):\n",
    "            if (board[i][j] == 'Q'):\n",
    "                return False\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "        # 扫描右上\n",
    "        i = row - 1\n",
    "        j = col + 1\n",
    "        while (i >= 0 and j < n):\n",
    "            if (board[i][j] == 'Q'):\n",
    "                return False\n",
    "            i -= 1\n",
    "            j += 1\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res_g = []\n",
    "    def generateBorad(self, n:int, pos:List[int]):\n",
    "        board = []\n",
    "        for i in range(n):\n",
    "            row = ['.'] * n\n",
    "            row[pos[i]] = 'Q'\n",
    "            board.append(\"\".join(row))\n",
    "        return board\n",
    "\n",
    "    def isVaild(self, pos:List[int], row:int, col:int):\n",
    "        for i in range(row):\n",
    "            if col == pos[i] or abs(row - i) == abs(col - pos[i]):\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "    def recursion(self, n:int, row:int, pos:List[int], res:List[List[int]]):\n",
    "        if row == n:\n",
    "            board = self.generateBorad(n, pos)\n",
    "            res.append(board)\n",
    "            return res\n",
    "        for i in range(n):\n",
    "            if self.isVaild(pos, row, i):\n",
    "                pos[row] = i\n",
    "                res = self.recursion(n, row + 1, pos, res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        res = []\n",
    "        pos = [0] * n\n",
    "        res = self.recursion(n, 0, pos, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "                    \n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "                    \n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "def isAvoid(a,b):\n",
    "    if a[0]==b[0] or a[1]==b[1]:\n",
    "        return False\n",
    "    if b[0]-a[0]==a[1]-b[1]:\n",
    "        return False\n",
    "    if b[0]-a[0]==b[1]-a[1]:\n",
    "        return False\n",
    "    return True\n",
    "def isAvoidAll(preQueens,pos):\n",
    "    l=len(preQueens)\n",
    "    for i,queen in enumerate(preQueens):\n",
    "        if not isAvoid([i,queen],[l,pos]):\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans=[]\n",
    "    def fillAns(self,res,n):\n",
    "        tmp1=[]\n",
    "        tmp2=[]\n",
    "        for i in res:\n",
    "            s='.'*i+'Q'+'.'*(n-1-i)\n",
    "            tmp1.append(s)\n",
    "            tmp2.append(s[::-1])\n",
    "        self.ans.append(tmp1)\n",
    "        if tmp1[0]!=tmp2[0]:\n",
    "            self.ans.append(tmp2)\n",
    "    def queen(self,preQueens,n):\n",
    "        l=len(preQueens)\n",
    "        for j in range(n):\n",
    "            if isAvoidAll(preQueens,j):\n",
    "                if l==n-1:\n",
    "                    res=preQueens+[j]\n",
    "                    self.fillAns(res,n)\n",
    "                else:\n",
    "                    self.queen(preQueens+[j],n)\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        if n==0:\n",
    "            return [[]]\n",
    "        if n==1:\n",
    "            return [['Q']]\n",
    "        for i in range(math.ceil(n/2)):\n",
    "            preQueen=[i]\n",
    "            self.queen(preQueen,n)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        board = [['.'] * n for _ in range(n)]\n",
    "        self.backtrack(board, 0)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, board, row):\n",
    "        n = len(board)\n",
    "        if row == n:\n",
    "            self.res.append([\"\".join(i) for i in board])\n",
    "        for col in range(n):\n",
    "            if self.is_valid(board, row, col):\n",
    "                board[row][col] = 'Q'\n",
    "                self.backtrack(board, row + 1)\n",
    "                board[row][col] = '.'\n",
    "\n",
    "    def is_valid(self, board, row, col):\n",
    "        n = len(board)\n",
    "        for i in range(row):\n",
    "            if board[i][col] == 'Q':\n",
    "                return False\n",
    "        i, j = row-1, col-1\n",
    "        while i >= 0 and j >= 0:\n",
    "            if board[i][j] == 'Q':\n",
    "                return False\n",
    "            i, j = i-1, j-1\n",
    "        i, j = row - 1, col + 1\n",
    "        while i >= 0 and j < n:\n",
    "            if board[i][j] == 'Q':\n",
    "                return False\n",
    "            i, j = i - 1, j + 1\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        res_all = []\n",
    "        def recursion(row, index):\n",
    "            if n == len(row):\n",
    "                res_all.append(row)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    flag = True\n",
    "                    for j in range(index+1):\n",
    "                        if row[j] == i:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag:\n",
    "                        for j in range(index+1):\n",
    "                            if abs(row[j]-i) == index+1-j:\n",
    "                                flag = False\n",
    "                                break\n",
    "                    if flag:\n",
    "                        recursion(row+[i], index+1)\n",
    "        \n",
    "        # recursion([], -1)\n",
    "        for i in range(n):\n",
    "            recursion([i], 0)\n",
    "        return [[\".\"*j+\"Q\"+\".\"*(n-1-j) for j in i] for i in res_all]\n",
    "        # print(res_all)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def helper(i):\n",
    "            if i == n:\n",
    "                res.append([])\n",
    "                for ni in range(n):\n",
    "                    board[info[ni]] = 'Q'\n",
    "                    res[-1].append(''.join(board))\n",
    "                    board[info[ni]] = '.'\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if j in a or i-j in b or i+j in c:\n",
    "                    continue\n",
    "                info[i] = j\n",
    "                a.add(j)\n",
    "                b.add(i-j)\n",
    "                c.add(i+j)\n",
    "                helper(i+1)\n",
    "                a.remove(j)\n",
    "                b.remove(i-j)\n",
    "                c.remove(i+j)\n",
    "        \n",
    "        a = set()\n",
    "        b = set()\n",
    "        c = set()\n",
    "        res = []\n",
    "        board = ['.'] * n\n",
    "        info = [-1] * n \n",
    "        helper(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        a = [0] * n\n",
    "        b = defaultdict(int)\n",
    "        c = defaultdict(int)\n",
    "        path = []\n",
    "        res = []\n",
    "        def backtrack(n, col):\n",
    "            if col == n:\n",
    "                res.append(path[:])\n",
    "            for i in range(n):\n",
    "                if a[i] == 0 and b[col + i] == 0 and c[col - i] == 0:\n",
    "                    a[i] = 1\n",
    "                    b[col + i] = 1\n",
    "                    c[col - i] = 1\n",
    "                    path.append(i)\n",
    "                    backtrack(n, col + 1)\n",
    "                    a[i] = 0\n",
    "                    b[col + i] = 0\n",
    "                    c[col - i] = 0\n",
    "                    path.pop()\n",
    "        backtrack(n, 0)\n",
    "        ans = []\n",
    "        for nums in res:\n",
    "            tmp = []\n",
    "            for num in nums:\n",
    "                s = \".\" * (num) + \"Q\" + \".\" * (n - num - 1)\n",
    "                tmp.append(s)\n",
    "            ans.append(tmp)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        # self.row = [0] * n\n",
    "        self.col = [0] * n\n",
    "        self.diag_p = [0] * (2 * n - 1)\n",
    "        self.diag_n = [0] * (2 * n + 1)\n",
    "        self.res = []\n",
    "\n",
    "        def dfs(cnt, path):\n",
    "            if cnt == n:\n",
    "                self.res.append(self.print(path))\n",
    "            \n",
    "            row = cnt\n",
    "            for col in range(n):\n",
    "                if self.col[col] == 0 and self.diag_p[row + col] == 0 and self.diag_n[row - col + n] == 0:\n",
    "                    self.col[col] = 1\n",
    "                    self.diag_p[row + col] = 1\n",
    "                    self.diag_n[row - col + n] = 1\n",
    "                    dfs(row + 1, path + [[row, col]])\n",
    "                    self.col[col] = 0\n",
    "                    self.diag_p[row + col] = 0\n",
    "                    self.diag_n[row - col + n] = 0\n",
    "        \n",
    "        dfs(0, [])\n",
    "        return self.res\n",
    "            \n",
    "\n",
    "\n",
    "    def print(self, points):\n",
    "        n = len(points)\n",
    "        data = [[0] * n for _ in range(n)]\n",
    "        for x, y in points:\n",
    "            data[x][y] = 1\n",
    "        res = []\n",
    "        tran_dict = {0:\".\", 1:\"Q\"}\n",
    "        for line in data:\n",
    "            res.append(\"\".join([tran_dict[x] for x in line]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "\n",
    "        def dfs(pre, i):\n",
    "            if i == n:\n",
    "                cur = [['.'] * n for _ in range(n)]\n",
    "                for i in range(n):\n",
    "                    cur[i][pre[i]] = 'Q'\n",
    "                queen.append([''.join(r) for r in cur])\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if j not in col and i - j not in right and i + j not in left:\n",
    "                    col.add(j)\n",
    "                    right.add(i - j)\n",
    "                    left.add(i + j)\n",
    "                    dfs(pre + [j], i + 1)\n",
    "                    col.discard(j)\n",
    "                    right.discard(i - j)\n",
    "                    left.discard(i + j)\n",
    "            return\n",
    "\n",
    "        col = set()\n",
    "        right = set()\n",
    "        left = set()\n",
    "        queen = []\n",
    "        dfs([], 0)\n",
    "        return queen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        col = set()\n",
    "        dignol1 = set()\n",
    "        dignol2 = set()\n",
    "\n",
    "        res = []\n",
    "        Q = [[\".\"] * n for i in range(n)]\n",
    "\n",
    "        def trackback(idx, col, dignol1, dignol2):\n",
    "            \n",
    "            if idx == n:\n",
    "                res.append([\"\".join(i) for i in Q.copy()])\n",
    "                return\n",
    "\n",
    "            for j in range(n):\n",
    "                if j in col or (idx - j )in dignol1 or idx + j in  dignol2:\n",
    "                    continue\n",
    "                Q[idx][j] = \"Q\"\n",
    "                col.add(j)\n",
    "                dignol1.add(idx - j)\n",
    "                dignol2.add(idx + j)\n",
    "                trackback(idx + 1, col, dignol1, dignol2)\n",
    "                Q[idx][j] = \".\"\n",
    "                col.remove(j)\n",
    "                dignol1.remove(idx - j)\n",
    "                dignol2.remove(idx + j)\n",
    "        \n",
    "        trackback(0, col, dignol1, dignol2)\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        column = [0] * n\n",
    "        row_minus_col = set()\n",
    "        row_plus_col = set()\n",
    "        row = [-1] *n\n",
    "        result_list = []\n",
    "        board_list = []\n",
    "\n",
    "        def solve(i):\n",
    "            for j in range(n):\n",
    "                if column[j] == 0 and i-j not in row_minus_col and i+j not in row_plus_col:                   \n",
    "                    flag = True\n",
    "                    row[i] = j\n",
    "                    if i == n-1:\n",
    "                        result_list.append(row.copy())\n",
    "                        break\n",
    "                    else:\n",
    "                        column[j] = 1\n",
    "                        row_minus_col.add(i-j)\n",
    "                        row_plus_col.add(i+j)\n",
    "                        solve(i+1)\n",
    "                        row[i] = -1\n",
    "                        column[j] = 0\n",
    "                        row_minus_col.remove(i-j)\n",
    "                        row_plus_col.remove(i+j)\n",
    "\n",
    "        solve(0)\n",
    "        board_list = []\n",
    "        for i in result_list:\n",
    "            board_list.append([i[j]*'.'+'Q'+(n-i[j]-1)*'.' for j in range(n)])\n",
    "\n",
    "        return board_list\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        mat = [['.'] * n for _ in range(n)]\n",
    "        \n",
    "        def backtracing(mat, res, cur_row):\n",
    "            if cur_row == n:\n",
    "                res.append([''.join(line) for line in mat])\n",
    "                return \n",
    "\n",
    "            for col in range(n):\n",
    "                # print(mat, self.isValid(cur_row, col, n, mat))\n",
    "                if self.isValid(cur_row, col, n, mat) == True:\n",
    "                    mat[cur_row][col] = 'Q' \n",
    "                    backtracing(mat, res, cur_row + 1)\n",
    "                    mat[cur_row][col] = '.'\n",
    "        \n",
    "        res = []\n",
    "        backtracing(mat, res, 0)\n",
    "        # print(res) \n",
    "        return res \n",
    "    \n",
    "    def isValid(self, x, y, n, mat) -> bool:\n",
    "        row = x\n",
    "        for col in range(n):\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "        \n",
    "        col = y \n",
    "        for row in range(n):\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "        \n",
    "        row = x\n",
    "        col = y\n",
    "        while row >= 0 and col >= 0 and row < n and col < n:\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "            row -= 1\n",
    "            col -= 1\n",
    "\n",
    "        row = x\n",
    "        col = y\n",
    "        while row >= 0 and col >= 0 and row < n and col < n:\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "            row -= 1\n",
    "            col += 1\n",
    "\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        mat = [['.'] * n for _ in range(n)]\n",
    "        \n",
    "        def backtracing(mat, res, cur_row):\n",
    "            if cur_row == n:\n",
    "                res.append([''.join(line) for line in mat])\n",
    "                return \n",
    "\n",
    "            for col in range(n):\n",
    "                # print(mat, self.isValid(cur_row, col, n, mat))\n",
    "                if self.isValid(cur_row, col, n, mat) == True:\n",
    "                    mat[cur_row][col] = 'Q' \n",
    "                    backtracing(mat, res, cur_row + 1)\n",
    "                    mat[cur_row][col] = '.'\n",
    "        \n",
    "        res = []\n",
    "        backtracing(mat, res, 0)\n",
    "        # print(res) \n",
    "        return res \n",
    "    \n",
    "    def isValid(self, x, y, n, mat) -> bool:\n",
    "        row = x\n",
    "        for col in range(n):\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "        \n",
    "        col = y \n",
    "        for row in range(n):\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "        \n",
    "        row = x\n",
    "        col = y\n",
    "        while row >= 0 and col >= 0 and row < n and col < n:\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "            row -= 1\n",
    "            col -= 1\n",
    "\n",
    "        row = x\n",
    "        col = y\n",
    "        while row >= 0 and col >= 0 and row < n and col < n:\n",
    "            if mat[row][col] == 'Q':\n",
    "                return False \n",
    "            row -= 1\n",
    "            col += 1\n",
    "\n",
    "        return True "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
